package practice_2025_9.practice_9_9;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    /**
     * 三角形的最小路径和
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m - 1).size();
        int[][] dp = new int[m][n + 1];
        // 初始化
        for(int i = 0; i < m; i++) {
            for(int j = 0; j <= n; j++) {
                dp[i][j] = 0x3f3f3f3f;
            }
        }
        // 填表
        dp[0][1] = triangle.get(0).get(0);
        for(int i = 1; i < m; i++) {
            int count = triangle.get(i).size();
            for(int j = 1; j <= count; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) +triangle.get(i).get(j - 1);
            }
        }
        int min = dp[m - 1][1];
        for(int i = 2; i <= n; i++) {
            min = Math.min(dp[m - 1][i], min);
        }
        return min;
    }

    /**
     * 单词拆分
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        // 字典中的单词能否拼出 s
        //dp[i]: 以 i 结尾的单词是否能由 list 拼出
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        Set<String> set = new HashSet<>(wordDict);
        dp[0] = true;
        s = " " + s;
        for(int i = 1; i <= len; i++) {
            for(int j = 0; j < i; j++) {
                // 剩下字符串: [j + 1, i]
                String tmp = s.substring(j + 1, i + 1);
                if (dp[j] && set.contains(tmp)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        // System.out.println(Arrays.toString(dp));
        return dp[len];
    }
}